package com.hy.treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class TreeNodeSearchByMax {


    /**
     * 515.在每个树行中找最大值
     * 力扣题目链接
     *
     * 您需要在二叉树的每一行中找到最大的值。
     *
     * @param root
     * @return
     */
    public List<Integer> levelOrderSearchByMax(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root == null){
            return res;
        }
        deque.offerLast(root);
        while (!deque.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int len = deque.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = deque.pollFirst();
                temp.add(node.val);

                if (node.left != null){
                    deque.offerLast(node.left);
                }
                if (node.right != null){
                    deque.offerLast(node.right);
                }
            }
            // 取出 每一层的最大值
            int maxNode = temp.stream().mapToInt(x -> x.intValue()).max().getAsInt();
            res.add(maxNode);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        TreeNodeSearchByMax treeNodeSearch = new TreeNodeSearchByMax();

        System.out.println("二叉树的每一行中找到最大的值 : "+ treeNodeSearch.levelOrderSearchByMax(root));
    }
}
